The present invention generally relates to the design automation of electronic logic circuits e.g. combinational circuits, finite state machines, and cascaded circuits. More particularly, the present invention relates to the synthesis of logic from symbolic high level languages.
It is known that in high level descriptions of logic circuits the ability to represent the values of some signals at a higher level of abstraction (i.e. with mnemonics) is greatly desirable. However, to construct a physical circuit the mnemonics must be assigned unique binary codes. It is known that the choice of binary codes has a dramatic effect on the speed, silicon area, and power consumption of the final implemented circuit.
Table 1 below gives an example of the binary encoding of 7 mnemonics of a logic circuit.
The minimum number of bits necessary to encode the mnemonics is p, where p is the smallest power of 2 such that 2p is greater than or equal to the number of mnemonics. Clearly in the example given in Table 1, 3 bit encoding is capable of coding for up to 8 mnemonics.
The above formula for p gives the minimal number of bits necessary for the encoding of the states of a logic circuit given by mnemonics. Thus, for 5 to 8 mnemonics at least 3 bits are needed, for 9 to 16 mnemonics at least 4 bits are needed, for 17 to 32 mnemonics at least 5 bits are needed, etc.
In the example given in Table 1, a unique binary encoding is given to each mnemonic. However, the choice of the binary encoding to be given to each mnemonic affects the speed area and power consumption of the implemented circuit. Thus, the task of choosing the binary codes is a key step in the implementation of circuits. Unfortunately, this task is very complex. Table 2 below shows the number of distinct minimal length encodings for circuits with various numbers of mnemonics.
As Table 2 shows, for circuits with nine mnemonics there are at least 10,810,800 distinct minimal length encodings. An exhaustive evaluation of each encoding is thus not feasible. The solution to the problem of the assignment of encodings to the mnemonics of the circuits have been the target of a great deal of work in the prior art. However, the problem of the prior art methods is that they are wholly heuristic and yield slow, area hungry and power hungry circuits.
In one prior art method disclosed in a paper by G De Micheli et al entitled xe2x80x9cOptimal State Assignment of Finite State Machinesxe2x80x9d (IEEE Transactions on Computer Aided Design, Vol. CAD-4, No. 3, July 1985, pages 269-285), a heuristic technique is used in which states which have the same next state and output for a given input are noted. These states are to be given adjacent assignments. Another heuristic is then used to define the complete code of each of the states so as to satisfy as many of the adjacency conditions as possible. This technique attempts to minimise the literal count. This technique is however limited since although it is known that the literal count is related to the area of the final circuit implementation in certain technologies, in other technologies such as field programmable gate arrays, literal count bears a weak relationship to the quality of the final implementation.
In another prior art method disclosed in a paper by T Villa and A Sangiovanni-Vincentelli entitled xe2x80x9cNOVA: State Assignment of Finite State Machine for Optimal Two-level Logic Implementationsxe2x80x9d (26th Design Automation Conference pp 327-332) a heuristic technique is used in which states which have the same next state and output for a given input are noted. These states are to be given adjacent assignments. An exact method is then used to satisfy all the adjacency conditions without necessarily using minimal length encoding. It is shown in the paper by experimental methods that this technique rarely yields a lower literal count than minimal length encoding. Moreover, better experiment results from those of the above method (G De Michele) are reported.
In another prior art method disclosed in a paper by J. Monterio et al entitled xe2x80x9cBitwise Encoding of Finite State Machinesxe2x80x9d (7th International Conference on VLSI Design, pages 379-382, January 1994), the states of a finite state machine are encoded iteratively to define the code word based on a heuristic. In this technique all bits are encoded sequentially in an attempt to once again minimise the number of literals. A limitation of this technique is that only the state transitions i.e. the next states are taken in consideration in the heuristic and no outputs of the finite state machine are taken into consideration.
FIG. 1 is a schematic diagram of a finite state machine which receives primary inputs and outputs primary outputs. The major component of the finite state machine is the combinational logic circuit 1 which acts on the primary inputs and present state variables (feedback inputs) to generate the primary outputs and next state variables (feedback outputs). The combinational logic circuit can be described by internal state representations i.e. mnemonics. In a finite state machine the next state of the machine is dependent on the inputs and the present state of the machine. Thus, the states of the finite state machines are output as feedback outputs and are stored in a state memory 2 which comprises flip-flops 2a, 2b and 2c: one per bit for representing the internal states of the finite state machine. FIG. 1 is represented as having internal states represented by 3 bit encodings with 3 bit encoded primary inputs and 3 bit encoded primary outputs.
Thus the inventors of the present invention have identified that in the approach of Monterio et al the omission of the consideration of the primary outputs and previously determined encoding bits in the heuristic reduces the effectiveness of the technique.
The approach by Monterio et al is also restricted to minimal length encoding and this does not always result in the best circuit from the viewpoint of area and/or speed.
Further, this approach uses a technique for the state assignment of finite state machines in which the finite state machine is decomposed by partitioning. This technique suffers from the disadvantage of the need to find preserved partitions in the set of mnemonic states. Such partitions are not always present.
It is thus an object of the present invention to provide a circuit design method and apparatus in which the disadvantages of the prior art methods are overcome and circuits of desired speeds, silicon area, and power consumption can be produced.
In accordance with a first aspect of the present invention, there is provided a method and apparatus for determining the binary encodings of a circuit which is in part heuristic and in part exact.
In this aspect of the present invention the inventors have realised that the assignment of binary encodings to a circuit can benefit from the use of the exact technique when the number of bits to be encoded is reduced. The number of bits to be encoded can be reduced by initially using a heuristic technique to determine the encodings of a number of bits thereby leaving only a limited number of bits left to be encoded. The exact technique can be used for the encoding of the last few bits to be determined.
The exact evaluation can be carried out using information on the preferred logic implementation e.g. Application Specific Integrated Circuits (ASIC""s) or Field Programmable Gate Arrays (PPGA""s). Thus this allows the preferred implementation to be taken into account during the state assignment.
In this aspect of the present invention, any conventional heuristic technique can be used for the encoding of the initial bits.
In this aspect of the present invention, the search can be successively divided into blocks by the encoding of initial bits using the heuristic technique. Each block is exhaustively evaluated in a determined sequence.
Either the literal count can be evaluated, or the evaluation can be made on any conventional synthesis tool relative to any conventional vendors library. As each block is evaluated, it is combined with the next block in the sequence and the mnemonics of this block are encoded relative to the encodings already obtained for the preceding block. In this way, the complete circuit is encoded in an incremental manner block-by-block so that the resulting circuit has the sane functionality as the original circuit.
The sequence of blocks to be evaluated is, in an embodiment, determined by identifying the block for which the number of next states not in the present states of the block is a minimum. For any next states which are not in the present states of the block, default encodings are used for these states thus allowing the evaluation of a virtual machine for which a small number of present states transit to unencoded next states within the set.
When the block has been encoded, it is combined with the logically adjacent blocks as defined by the partial encodings to determine a larger block which has the minimum number of unencoded next states not in the present states set for the large block. This large block then evaluated by setting any next states not in the set to the default value as before. In this way the encodings for the blocks are incrementally determined relative to the encodings already obtained for previous blocks.
An alternative way to determine the sequence of blocks is simply to order them according to the order of the gray code of the partial encoding.
In a second aspect of the present invention, the symbolic state representations for a circuit are encoded one bit at a time by repeatedly dividing the symbolic state representations into disjoint sets and assigning a one bit code to each of the states of the disjoint sets in dependence upon the divisions. The disjoint sets become smaller after each division and the divisions are determined in dependence upon the encoding of previous divisions.
Thus, in the repeated one bit encoding, a one bit code is assigned to each of the two disjoint sets generated by the division of either the state set or a previously generated disjoint set. The one bit code depends upon the manner in which the two disjoint sets were determined. At each repetition the combination of the thus far determined n divisions leads to at most 2n encoded disjoint sets, each set having associated with it a unique n-bit binary code.
The divisions are determined by identifying the set of next states transited to from a set of present states in response to some combination of the primary and feedback inputs. This set and its compliment define a division. This division is encoded with a one bit binary code. In a preferred embodiment the identified set is encoded with 1 and its compliment with 0. The encoded disjoint sets are subsequently themselves divided as more divisions are calculated. The divisions can be made sequentially for the necessary number of bits to binary encode the symbolic state representation. Alternatively, the division of the disjoint sets can stop when the set size reaches a predetermined set size at which the encoding of the states in the disjoint sets can be determined exactly as described hereinabove with regard to the previous aspect of the present invention.
The divisions do not necessarily comprise preserved partitions since they need not preserve cover in the set of next states. The set of next states for a set of present states can include other states not in the present state set. When assigning binary codes to the sets resulting from the division, in order to evaluate a block of the logic circuit resulting from the division of the circuit a default value can be used for these next states lying outside the present state set.
The repeated determination of divisions results in the repeated division of the logic circuit into blocks using the next state table. When there are a number of candidate divisions, a division can be chosen to save logic i.e. to reduce the number of literals.
At each stage of the division of the symbolic states into disjoint sets, there can be a number of possible divisions. In order to avoid having to proceed with encoding a larger number of possible divisions, in accordance with an embodiment of the present invention, for each encoded bit i.e. for each division, a cost of outputs of the circuit is determined and this is used in the determination of the optimum binary code for the encoded bit. The cost preferably comprises the cost of the primary outputs and any previously encoded bits. The cost can comprise the number of literals for the outputs and any previously encoded bits which form feedback outputs, and the optimum binary code is determined to minimise the number of literals. Thus in accordance with this embodiment, divisions can be chosen to take into account the number of literals. This can aid a search for the optimum encoding.
The identification of a set of next states which is a subset of all states is preferably achieved for a plurality of logically adjacent possible inputs. It is known that larger blocks of logically adjacent is result in a saving of logic.
This aspect of the present invention is applicable to both minimal length encoding and non minimal length encoding. For minimal length encoding, the number of bits used to binary encode the symbolic representations is a minimum. A non minimal length encoding, any number of bits can be used for encoding the symbolic representations. Whilst minimal length encoding will result in a minimum number of flip-flops, it may not result in the optimum circuit from the viewpoint of speed, area, or power consumption. For example, in field programmable gate array (FPGA""s), each logical component has built into it a flip-flop and whether this flip-flop is used or not does not affect the overall area of the circuit. For many implementations, non-minimal length encoding, whilst requiring more flip-flops, can result in a higher speed circuit. Thus, for non minimal length encoding, any subsequent division, when combined with all previous divisions, need only result in encoded disjoint sets in which at least one of the sets is smaller than before. For minimal length encoding, the number of next states in the disjoint sets must be up to half the number of present states rounded up to the nearest power of 2 and the compliment set must also contain up to half the number of present states rounded up to the nearest power of 2.
For minimal length encoding, where disjoint sets of the required size cannot be identified for an input, i.e. the sets are too small, sets of states for a plurality of different inputs can be unioned to form disjoint sets of the required size. Such disjoint sets do not in general result in the same logic saving since the plurality of inputs require a respective plurality of terms to define them. Logical adjacency is however provided for the unioned sets since they are assigned the same code for a binary bit (i.e. a feedback output).
In accordance with a third aspects the present invention provides a method and apparatus for optimising state assignments for a circuit. A full binary encoding of a circuit can be optimised using this technique. A plurality of the binary encoded bits are encoded at a least one symbolic representation. Thus, for a 32 bit binary encoded representation, any number of bits can be encoded symbolically and any number of symbolic representations can be provided for segments of the code. For example the first and last 16 bits can be encoded separately as segment x and segment y, the last 16 bits only can be encoded as segment y, or the first 8, next 8 and last 16 bits can be encoded as segment x, segment y, segment z.
Each of the symbolic representations resulting from this symbolic encoding can then be evaluated to determine the optimum binary codes for this symbolic representation having regard to any binary codes already provided.
The determination of the optimum binary codes can be achieved using any conventional technique including the techniques of the previously described aspects of the present invention.
This aspect of the present invention enables the tuning of the encoding already provided to obtain a more optimum binary encoding. Any number of the bits can be selected for optimisation and this can be repeated any number of times on various combinations of bits in order to try to optimise the encoding.
This aspect of the present invention is applicable to any type of logic circuit not just sequential logic circuits e.g. finite state machines. When the technique is applied to logic circuits for which the next state depends on the present state the technique of the previous aspects can be employed for the encoding.